from typing import List, Dict, Tuple
import time

class Level:
    """关卡类"""
    def __init__(self, 
                 level_id: int,
                 walls: List[Tuple[int, int]],
                 boxes: List[Tuple[int, int]],
                 targets: List[Tuple[int, int]],
                 player: Tuple[int, int],
                 description: str = "",
                 difficulty: int = 1):
        self.level_id = level_id
        self.walls = walls
        self.boxes = boxes
        self.targets = targets
        self.player = player
        self.description = description
        self.difficulty = difficulty
        
    def validate(self) -> bool:
        """验证关卡数据是否有效"""
        # 检查墙壁是否形成封闭空间
        if not self.walls:
            return False
            
        # 检查箱子数量与目标点数量是否匹配
        if len(self.boxes) != len(self.targets):
            return False
            
        # 检查玩家初始位置是否合法
        if self.player in self.walls:
            return False
            
        # 检查箱子初始位置是否合法
        for box in self.boxes:
            if box in self.walls:
                return False
                
        # 检查所有目标点是否可达
        if not self._are_targets_reachable():
            return False
                
        return True
        
    def _are_targets_reachable(self) -> bool:
        """检查所有目标点是否可达"""
        from heapq import heappush, heappop
        import time
        
        # 创建网格表示
        grid = {}
        # 首先确定网格边界
        min_x = min(p[0] for p in self.walls)
        max_x = max(p[0] for p in self.walls)
        min_y = min(p[1] for p in self.walls)
        max_y = max(p[1] for p in self.walls)
        
        # 填充网格
        for x in range(min_x, max_x + 1):
            for y in range(min_y, max_y + 1):
                if (x, y) in self.walls:
                    grid[(x, y)] = '#'
                elif (x, y) in self.boxes:
                    grid[(x, y)] = 'B'
                elif (x, y) == self.player:
                    grid[(x, y)] = 'P'
                else:
                    grid[(x, y)] = '.'  # 空位置
        
        # A*搜索算法
        def heuristic(a, b):
            return abs(a[0] - b[0]) + abs(a[1] - b[1])
            
        def a_star_search(start, goal):
            start_time = time.time()
            frontier = []
            heappush(frontier, (0, start))
            came_from = {}
            cost_so_far = {}
            came_from[start] = None
            cost_so_far[start] = 0
            
            while frontier:
                # 超时检查
                if time.time() - start_time > 1:  # 1秒超时
                    return False
                    
                _, current = heappop(frontier)
                
                if current == goal:
                    return True
                    
                for dx, dy in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
                    nx, ny = current[0] + dx, current[1] + dy
                    next_pos = (nx, ny)
                    
                    # 检查是否在网格边界内
                    if not (min_x <= nx <= max_x and min_y <= ny <= max_y):
                        continue
                        
                    # 检查是否是墙
                    if grid[next_pos] == '#':
                        continue
                        
                    new_cost = cost_so_far[current] + 1
                    if next_pos not in cost_so_far or new_cost < cost_so_far[next_pos]:
                        cost_so_far[next_pos] = new_cost
                        priority = new_cost + heuristic(goal, next_pos)
                        heappush(frontier, (priority, next_pos))
                        came_from[next_pos] = current
                        
            return False
            
        # 检查所有目标点是否可达
        for target in self.targets:
            if not a_star_search(self.player, target):
                return False
                
        return True

def initialize_levels():
    levels = [
        Level(
            level_id=1,
            walls=[(0, 0), (1, 0), (2, 0), (3, 0), (4, 0),
                  (0, 1), (4, 1),
                  (0, 2), (4, 2),
                  (0, 3), (4, 3),
                  (0, 4), (1, 4), (2, 4), (3, 4), (4, 4)],
            boxes=[(2, 2)],
            targets=[(2, 3)],
            player=(2, 1),
            description="入门关卡，熟悉基本操作",
            difficulty=1
        ),
        Level(
            level_id=2,
            walls=[(0, 0), (1, 0), (2, 0), (3, 0), (4, 0),
                  (0, 1), (4, 1),
                  (0, 2), (4, 2),
                  (0, 3), (4, 3),
                  (0, 4), (1, 4), (2, 4), (3, 4), (4, 4)],
            boxes=[(2, 2)],
            targets=[(2, 3)],
            player=(2, 1),
            description="最大复杂地图，终极挑战",
            difficulty=10
        ),
        Level(
            level_id=3,
            walls=[(0, 0), (1, 0), (2, 0), (3, 0), (4, 0), (5, 0),
                  (0, 1), (5, 1),
                  (0, 2), (5, 2),
                  (0, 3), (5, 3),
                  (0, 4), (1, 4), (2, 4), (3, 4), (4, 4), (5, 4)],
            boxes=[(1, 2), (3, 2), (4, 2)],
            targets=[(1, 3), (3, 3), (4, 3)],
            player=(2, 1),
            description="三箱挑战，需要更好的规划路线",
            difficulty=3
        ),
        Level(
            level_id=4,
            walls=[(0, 0), (1, 0), (2, 0), (3, 0), (4, 0), (5, 0),
                  (0, 2), (5, 2),
                  (0, 3), (5, 3),
                  (0, 4), (1, 4), (2, 4), (3, 4), (4, 4), (5, 4)],
            boxes=[(1, 2), (2, 2), (3, 2), (4, 2)],
            targets=[(1, 3), (2, 3), (3, 3), (4, 3)],
            player=(2, 1),
            description="四箱挑战，需要更复杂的策略",
            difficulty=4
        ),
        Level(
            level_id=5,
            walls=[(0, 0), (1, 0), (2, 0), (3, 0), (4, 0), (5, 0), (6, 0),
                  (0, 1), (6, 1),
                  (0, 2), (6, 2),
                  (0, 3), (6, 3),
                  (0, 4), (1, 4), (2, 4), (3, 4), (4, 4), (5, 4), (6, 4)],
            boxes=[(1, 2), (2, 2), (4, 2), (5, 2)],
            targets=[(1, 3), (2, 3), (4, 3), (5, 3)],
            player=(3, 1),
            description="更大场地，更多障碍",
            difficulty=5
        ),
        Level(
            level_id=6,
            walls=[(0, 0), (1, 0), (2, 0), (3, 0), (4, 0), (5, 0), (6, 0),
                  (0, 1), (6, 1),
                  (0, 2), (6, 2),
                  (0, 3), (6, 3),
                  (0, 4), (1, 4), (2, 4), (3, 4), (4, 4), (5, 4), (6, 4)],
            boxes=[(1, 2), (2, 2), (3, 2), (4, 2), (5, 2)],
            targets=[(1, 3), (2, 3), (3, 3), (4, 3), (5, 3)],
            player=(3, 1),
            description="五箱挑战，考验耐心和策略",
            difficulty=6
        ),
        Level(
            level_id=7,
            walls=[(0, 0), (1, 0), (2, 0), (3, 0), (4, 0), (5, 0), (6, 0), (7, 0),
                  (0, 1), (7, 1),
                  (0, 2), (7, 2),
                  (0, 3), (7, 3),
                  (0, 4), (1, 4), (2, 4), (3, 4), (4, 4), (5, 4), (6, 4), (7, 4)],
            boxes=[(1, 2), (2, 2), (3, 2), (5, 2), (6, 2)],
            targets=[(1, 3), (2, 3), (3, 3), (5, 3), (6, 3)],
            player=(4, 1),
            description="复杂地形，需要精确操作",
            difficulty=7
        ),
        Level(
            level_id=8,
            walls=[(0, 0), (1, 0), (2, 0), (3, 0), (4, 0), (5, 0), (6, 0), (7, 0),
                  (0, 1), (7, 1),
                  (0, 2), (7, 2),
                  (0, 3), (7, 3),
                  (0, 4), (1, 4), (2, 4), (3, 4), (4, 4), (5, 4), (6, 4), (7, 4)],
            boxes=[(1, 2), (2, 2), (3, 2), (4, 2), (5, 2), (6, 2)],
            targets=[(1, 3), (2, 3), (3, 3), (4, 3), (5, 3), (6, 3)],
            player=(4, 1),
            description="六箱挑战，终极考验",
            difficulty=8
        ),
        Level(
            level_id=9,
            walls=[(0, 0), (1, 0), (2, 0), (3, 0), (4, 0), (5, 0), (6, 0), (7, 0), (8, 0), (9, 0),
                  (0, 1), (9, 1),
                  (0, 2), (9, 2),
                  (0, 3), (9, 3),
                  (0, 4), (1, 4), (2, 4), (3, 4), (4, 4), (5, 4), (6, 4), (7, 4), (8, 4), (9, 4)],
            boxes=[(1, 2), (2, 2), (3, 2), (5, 2), (6, 2), (7, 2)],
            targets=[(1, 3), (2, 3), (3, 3), (5, 3), (6, 3), (7, 3)],
            player=(4, 1),
            description="大师级挑战，需要完美策略",
            difficulty=9
        ),
        Level(
            level_id=10,
            # walls=[(0, 0), (1, 0), (2, 0), (3, 0), (4, 0), (5, 0), (6, 0), (7, 0),
            #       (0, 1), (7, 1),
            #       (0, 2), (7, 2),
            #       (0, 3), (7, 3),
            #       (0, 4), (1, 4), (2, 4), (3, 4), (4, 4), (5, 4), (6, 4), (7, 4),
            #       (2, 1), (3, 1),
            #       (5, 1), (6, 1),
            #       (1, 2), (4, 2),
            #       (2, 3), (5, 3)],
            walls=[(0, 0), (1, 0), (2, 0), (3, 0), (4, 0), (5, 0), (6, 0), (7, 0), (8, 0), (9, 0),
                  (0, 1), (9, 1),
                  (0, 2), (9, 2),
                  (0, 3), (9, 3),
                  (0, 4), (9, 4),
                  (0, 5), (9, 5),
                  (0, 6), (1, 6), (2, 6), (3, 6), (4, 6), (5, 6), (6, 6), (7, 6), (8, 6), (9, 6),
                  # 内部墙壁
                  (2, 1), (4, 1),
                  (8, 1), (8, 4),
                  (4, 4), (7, 5)],
            boxes=[(6, 3), (4, 2), (6, 2),
                  (2, 3), (5, 3)],
            targets=[(1, 3), (4, 3), (6, 3),
                    (2, 5), (5, 4)],
            player=(3, 2), 
            description="终极挑战，需要完美策略和耐心",
            difficulty=10
        )
    ]
    
    # 验证所有关卡
    for level in levels:
        if not level.validate():
            raise ValueError(f"关卡 {level.level_id} 数据无效")
            
    # 解锁第一关
    levels[0].is_unlocked = True
    
    return levels

# 初始化关卡数据
LEVELS = initialize_levels()
